In the field of digital communications, digital information is conveyed from a transmitter to a receiver through a channel. “Channel” is a generalized term that can include many things. For instance, in satellite communication systems, the channel consists of the atmosphere between an earth-bound transmitter and a satellite. In data storage devices, such as magnetic disc drives, the channel includes a storage medium where the signal is stored for some period of time before being delivered to the receiver.
All channels introduce noise into the signals they convey. To detect and sometimes to correct errors caused by this channel noise, the art has developed a large number of coding techniques. These coding techniques convert data words formed of “m” data bits into larger code words formed of “n” code bits. The additional bits in the code words permit the detection and sometimes the correction of errors in the signals received from the channel.
The ratio of the number of data bits to the number of code bits, m/n, is known as the code rate of the code. In general, the ability to detect and correct errors in a received signal increases as the code rate decreases because a lower code rate means a greater number of additional bits in the code word. However, each additional bit added by the encoder increases the time and energy needed to transmit the signal through the channel. Thus, to minimize the time and energy needed to send the code, the code rate should be maximized.
In one type of coding, known as Non-Return-to-Zero Inverse (NRZI), every digital one in a code word is represented by a transition in the transmitted signal, and every digital zero is represented by a lack of transitions in the transmitted signal. To allow the receiver to generate a clock signal from the received signal, the encoded signal is generally limited so that the number of consecutive zeros is no greater than a maximum number “k”. This kind of code is known as a run-length-limited (RLL) code with a “k” constraint.
In order for a RLL code to satisfy the “k” constraint, m bits of data pattern must be mapped into n bits of code pattern that satisfy the RLL constraints. Since the constrained code pattern is a subset of the unconstrained data pattern, the value of “n” must be greater than “m”. In other words, the code rate m/n must be less than one and usually this ratio increases as the value of “k” is increased in the design of a RLL code. The highest achievable code rate for a particular “k” is known as the capacity of that code. For an efficient storage channel, the higher the code rates the better. The efficiency of the code is measured by comparing the code rate against the code capacity.
To achieve higher code rates, the number of bits being encoded can be increased. For example, a 64/65 code has a higher code rate than a 17/18 code. However, with each additional bit in the input data word, the number of possible input data words increases by a multiple of 2. Thus, there are twice as many possible 64-bit data words (264) as there are 63-bit data words (263).
For even modest data word sizes, the number of available data words makes encoding through a simple table look-up inefficient. For example, for a word length of 20 bits, a table look-up encoding scheme would need to search a database of 220 (1,048,576) entries. Thus, a system is needed for producing RLL codes that have a high code rate and also have a high efficiency.
The present invention provides a solution to this and other problems, and offers other advantages over the prior art.